//
// Created by xili on 2024/9/19 19:28.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    string removeDuplicateLetters(string s) {
        //统计每个字符出现的次数
        vector<int> cnt(26, 0);
        for (auto &it: s) {
            cnt[it - 'a']++;
        }
        //是否入栈
        vector<bool> in(26, false);
        stack<char> st;
        for (auto &it: s) {
            //当前元素没有进栈
            if (!in[it - 'a']) {
                //当栈不为空 栈顶元素大于当前元素 后面还有栈顶元素时
                while (!st.empty() && st.top() > it && cnt[st.top() - 'a'] > 0) {
                    in[st.top() - 'a'] = false;
                    st.pop();
                }
                st.push(it);
                in[it - 'a'] = true;
            }
            cnt[it - 'a']--;
        }
        string ans = "";
        while (!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};